/**
 * @description At least a few coins are required to make up the target amount
 * @param coins coin types
 * @param target target amount
 */
const cache: any = {};
const resultAll: {
  [props: number]: number[][];
} = {};
export const changeCoins = (coins: number[], target: number) => {
  const makeMin = (value) => {
    if (!value) {
      return [];
    }
    if (cache[value]) {
      return cache[value];
    }

    let min: number[] =[];
    let newMin: number[] = [];

    for (let coin of coins) {
      let newTarget = value - coin;
      if (newTarget >= 0) {
        newMin = makeMin(newTarget);
      }

      if (
        newTarget >= 0
        && (newMin.length || !newTarget)
      ) {
        if (resultAll[value]) {
          resultAll[value].push([coin].concat(newMin));
        } else {
          resultAll[value] = [[coin].concat(newMin)];
        }
      }

      if (
        newTarget >= 0
        && (newMin.length < min.length - 1 || !min.length)
        && (newMin.length || !newTarget)
      ) {
        min = [coin].concat(newMin);
      }
    }
    
    cache[value] = min;
    return min;
  };

  return makeMin(target);
};

export const changeCoinsGreedy = (coins: number[], target: number) => {
  const result: number[] = [];
  const coinsNew = coins.sort((a, b) => b - a);
  
  let targetNew = target;
  for (let i = 0; i < coinsNew.length; i++) {
    while(targetNew > 0) {
      targetNew-=coinsNew[i];
      if (targetNew >= 0) {
        result.push(coinsNew[i]);
      }
    }
    if (targetNew < 0) {
      targetNew+=coinsNew[i];
    }
    if (targetNew === 0) {
      break;
    }
  }

  return result;
};
